უმოკლესი გზების პოვნა მიმართულ
აციკლურ გრაფში (Directed Acyclic Graph).
დეიქსტრას (Dijkstra) ალგორითმი უმოკლესი
გზების საპოვნელად.
მარიამ გობრონიძე
ამ პრეზენტაციაში განვიხილავთ ერთ-ერთ ყველაზე ცნობილ
უმოკლესი გზის პოვნის ალგორითმს — დეიქსტრას ალგორითმს,
რომელიც შეიმუშავა ჰოლანდიელმა კომპიუტერულმა მეცნიერმა
ედსგერ ვ. დეიკსტრამ 1956 წელს. აგრეთვე განვიხილავთ
ალგორითმის სირთულეს.
რა არის დეიკსტრას ალგორითმი?
ალგორითმის აღწერა
დეიქსტრას ალგორითმი არის ერთ-ერთი ყველაზე პოპულარული
ალგორითმი ერთწყაროიან Shortest Path (უმოკლესი გზის) ამოცანის
გადასაჭრელად ისეთ გრაფებში, რომელთა წიბოების წონები
არაუარყოფითი რიცხვებია. მისი მიზანია, იპოვოს ორი წვეროს
შორის უმოკლესი მანძილი.
ალგორითმის აღწერა
ალგორითმი ინახავს მონხულებულ და მოუნახულებელ წვეროთა
სიმრავლეს. იგი იწყება საწყისი წვეროდან და ყოველ ჯერზე ირჩევს
იმ მოუნახულებელ წვეროს, რომლამდეც სავარაუდო მანძილი
ყველაზე მცირეა. შემდეგ ის განიხილავს ამ წვეროს მეზობელ
წვეროებს და განაახლებს მათ მანძილს, თუ აღმოაჩენს უფრო მოკლე
გზას. ეს პროცესი გრძელდება მანამ, სანამ მივაღწევთ სამიზნე
წვეროს ან ყველა წვდომად წვეროს არ მოვინახულებთ.
დეიქსტრას ალგორითმს შეუძლია იმუშაოს როგორც მიმართულ,
ასევე არამიმართულ გრაფებზე, თუ გრაფი აკმაყოფილებს ორ
პირობას:
● წიბოების წონები არ უნდა იყოს უარყოფითი.
● გრაფი უნდა იყოს ბმული (connected).
მიმართულ გრაფში თითოეულ წიბოს აქვს მიმართულება, ხოლო
არამიმართულში — შესაძლებელია მოძრაობა ორივე
მიმართულებით.
დეიქსტრას ალგორითმის ეტაპები:
• მიანიჭე საწყის წვეროს მანძილი 0, დანარჩენებს კი უსასრულობა
(∞).
• აირჩიე ის წვერო, რომელიც ჯერ არ არის მონახულებული და
აქვს ყველაზე მცირე დროებითი მანძილი.
• განიხილე ამ წვეროს მეზობელი წვეროები:
• თუ ამ გზით მიღებული მანძილი უფრო მცირეა, განაახლე შესაბამისი
წვეროს დროებითი მანძილი.
• მონიშნე მიმდინარე წვერო, როგორც მონახულებული.
• გაიმეორე ნაბიჯები 2–4 მანამ, სანამ ყველა წვერო არ იქნება
მონახულებული.
0
Example Graph
2 4
6
8 10 2
3
2 5 15 6
1 5
Dijkstra's Algorithm
6
WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE
როგორ მუშაობს დეიკსტრას ალგორითმი?
დავუშვათ, გრაფში გვაქვს 7 წვერო (0–6) და დავიწყებთ მუშაობას
წვეროდან 0. საწყის ეტაპზე მანძილები იქნება:
0 → 0, 1 → ∞, 2 → ∞, 3 → ∞, 4 → ∞, 5 → ∞, 6 → ∞
გვექნება აგრეთვე მოუნახული წვეროების მასივი , რომელიც მოგვითხრობს ჯერ
კიდევ მოუნიშნავ (ანუ არამონახულებულ ) კვანძებზე .
ალგორითმი დასრულდება მაშინ , როცა ყველა კვანძი მოინიშნება როგორც
მონახულებული და მათ შორის არსებული მანძილები დაემატება გზას .
STEP 1
이
Start from Node 0 and mark Node 0 as Visited and check for adjacent nodes
2 4
Unvisited Nodes
{0,1,2,3,4,5,6}
6 8 10 2
Distance:
3
6
0:0
1:
2: 0o 2 5 15 6
3: S
1 5
4:
5: ∞
6: 8
Dijkstra's Algorithm
WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE
ნაბიჯი 2: შევამოწმოთ მეზობელი კვანძები . გვაქვს ორი არჩევანი — ან
ავირჩიოთ კვანძი 1, რომლის წონა არის 2, ან კვანძი 2, რომლის წონა არის 6.
უნდა ავირჩიოთ მინიმალური წონის მქონე კვანძი . ამ ნაბიჯში მინიმალური
მანძილის მეზობელი კვანძი არის კვანძი 1, ამიტომ მოვნიშნავთ მას როგორც
მონახულებულს და დავამატებთ მანძილს მთელ გზას .
მანძილი : კვანძი 0 -> კვანძი 1 = 2
STEP 2
이
Mark Node 1 as Visited and add the Distance
2 4
6 8 10 2
Unvisited Nodes
{0,1,2,3,4,5,6}
Distance:
3
6
0:0 ☑
1: 2 ☑
2: 2 5 15 6
3: 1 5
4:
5:∞
6: ∞
Dijkstra's Algorithm
WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE
ნაბიჯი 3. შემდეგ გადავადგილდეთ წინ და შევამოწმოთ მეზობელი კვანძი , რომელიც
არის კვანძი 3. მოვნიშნავთ მას როგორც მონახულებულს და დავამატებთ მანძილს .
საერთო მანძილი იქნება :
მანძილი : კვანძი 0 -> კვანძი 1 -> კვანძი 3 = 2 + 5 = 7
STEP 3
0
Mark Node 3 as Visited after considering the Optimal path and add the Distance
2 4
6 8 10 2
Unvisited Nodes
(0,1,2,3,4,5,6}
Distance:
3
6
0:0 ☑
1: 2
2:6 2 5 15 6
3:7 1 5
4: C
5:
6: c
Dijkstra's Algorithm
WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE WWW.BTU.EDU.GE
ნაბიჯი 4: კვლავ გვაქვს ორი არჩევანი მეზობელი კვანძებისთვის — ან ავირჩიოთ
კვანძი 4, რომლის მანძილი არის 10, ან კვანძი 5, რომლის მანძილი არის 15. უნდა
ავირჩიოთ მინიმალური მანძილის მქონე კვანძი . ამ ეტაპზე მინიმალური მანძილის
მქონე მეზობელი კვანძი არის კვანძი 4, ამიტომ მოვნიშნავთ მას როგორც
მონახულებულს და დავამატებთ მანძილს .
მანძილი : კვანძი 0 -> კვანძი 1 -> კვანძი 3 -> კვანძი 4 = 2 + 5 + 10 = 17
ნაბიჯი 5: კვლავ გადავადგილდეთ წინ და შევამოწმოთ მეზობელი კვანძი ,
რომელიც არის კვანძი 6. მოვნიშნავთ მას როგორც მონახულებულს და
დავამატებთ მანძილს . საერთო მანძილი იქნება :
მანძილი : კვანძი 0 -> კვანძი 1 -> კვანძი 3 -> კვანძი 4 -> კვანძი 6 = 2 + 5 +
10 + 2 = 19
რატომ ვერ მუშაობს დეიქსტრას ალგორითმი
უარყოფითი წიბოების მქონე გრაფებზე?
დეიქსტრას ალგორითმი ეყრდნობა იდეას, რომ როცა წვერო მონახულებულია, მისი მანძილი
აღარ შეიცვლება. თუმცა, თუ არსებობს უარყოფითი წიბო, შესაძლოა მოგვიანებით მოიძებნოს
უკეთესი გზა, რაც ამ ალგორითმმა ვერ დააფიქსიროს.
ამიტომ, უარყოფითი წიბოების შემთხვევაში უმჯობესია გამოვიყენოთ Bellman-Ford-ის
ალგორითმი .
დასკვნა
საერთო ჯამში, დეიქსტრას ალგორითმი არის მარტივი და ეფექტური გზა Shortest Path
ამოცანის გადასაჭრელად იმ გრაფებში, სადაც წიბოების წონები არ არის უარყოფითი.
თუმცა, უარყოფითი წიბოების ან ციკლების შემთხვევაში საჭიროა უფრო მოქნილი
ალგორითმების — Bellman-Ford ან Floyd-Warshall-ის — გამოყენება.
ვიპოვოთ უმოკლესი გზა საწყისი s წვეროდან ყველა დანარჩენ
წვერომდე, მიმართულ აციკლურ წონიან გრაფში.
ამოცანა
ზოგადი წონიანი გრაფისთვის ერთ წვეროდან ყველა წვერომდე უმოკლესი ბილიკის
პოვნა შესაძლებელია Bellman–Ford-ის ალგორითმით დროით O(VE). თუ გრაფში
უარყოფითი წონები არ გვხვდება, უკეთესი შედეგის მიღება შესაძლებელია Dijkstra-ს
ალგორითმით დროით O(E + V log V).
შესაძლებელია კიდევ უფრო ეფექტური ალგორითმის გამოყენება მიმართული და
აციკლური გრაფებისთვის. კონკრეტულად კი, უმოკლესი ბილიკების პოვნა
შესაძლებელია O(V + E) დროში, ტოპოლოგიური დალაგების გამოყენებით
• მივანიჭოთ საწყის წვეროს მნიშვნელობად 0, დანარჩენებს კი
უსასრულობა (∞);
• დავალაგოთ გრაფი ტოპოლოგიურად;
• მას შემდეგ რაც გვაქვს ტოპოლოგიური დალაგება (ანუ წრფივი
წარმოდგენა), თითოეულ კვანძს ვამუშავებთ თანმიმდევრობით.
ყოველი მიმდინარე კვანძის დამუშავებისას, ვაახლებთ მის
მეზობელ კვანძებთან მანძილებს ამ კვანძის მანძილის
გამოყენებით.
ინიციალიზაცია:
   dist[] = {∞, ∞, ..., ∞}, dist[source] = 0
შეადგინე გრაფის ტოპოლოგიური მიმდევრობა.
ყოველი წვეროსთვის u ტოპოლოგიური მიმდევრობიდან:
   ყოველი მისი მიმდებარე წვეროსთვის v:
     თუ dist[v] > dist[u] + weight(u, v)
       მაშინ განაახლე: dist[v] = dist[u] + weight(u, v)
გმადლობთ ყურადღებისთვის!